//
// Created by 123 on 2024/3/23.
//
/**
 * 思想：通过点集邻接的边里取最小
 * 来不断地扩充点集
 */
#include <iostream>
#include <vector>
#include "../../6_树/并查集/union_look_up_set.cpp"

using namespace std;
#define VexNum 5


typedef struct Edge {
//    弧尾
    int r;
//    弧头
    int h;
//    权值
    int data;
//    是否加入树中
    bool flag;
} Edge;

typedef struct Graph {
    Edge *edges[1000];
    int size = 0;
} Graph;
string path[VexNum] = {"", "", "", "", ""};
//源点到各点的路径
string vex[VexNum] = {"V1", "V2", "V3", "V4", "V5"};
//源点到各点的权值
int value[VexNum]={99999,99999,99999,99999,99999,};
bool isVisited[VexNum] = {false, false, false, false, false};

//获得边，其实就是初始化一个边
Edge *getEdge(int r, int h, int data);

//添加边，网图中添加边集
void addEdge(Graph &graph, Edge *edge);

//获得该点指向的所有点
vector<Edge *> getPointVex(Graph graph, int v);



void dijkstra(Graph graph, int v) {
    path[v]=vex[v];
    value[v]=0;
    int begin_v=v;
    int count=0;
    while (count<VexNum){
//        获得该点下一步可以到达的点的信息
        vector<Edge * > vexs= getPointVex(graph,begin_v);

        for (int i = 0; i < vexs.size(); ++i) {
//            若当前点到下一点的权值小于其已有的值
//            就需要，更新数据
            if(value[begin_v]+vexs[i]->data<value[vexs[i]->h]){
                value[vexs[i]->h]=value[begin_v]+vexs[i]->data;
                path[vexs[i]->h]=path[begin_v]+"--->"+vex[vexs[i]->h];
            }
        }
//        下一个最优的点的信息
        int end_index=-1;
        int weight=9999;
        for (int i = 0; i < VexNum; ++i) {
            if(!isVisited[i]&&weight>value[i]){
                weight=value[i];
                end_index=i;
            }
        }
        isVisited[end_index]= true;
        begin_v=end_index;
        count++;
    }
}

void init(Graph &graph);

int main() {
    Graph graph;
    init(graph);
    dijkstra(graph,0);
    for (int i = 0; i < VexNum; ++i) {
        cout<<vex[i]<<": "<<value[i]<<":   "<<path[i]<<endl;
    }

}

void init(Graph &graph) {
    addEdge(graph, getEdge(0, 1, 10));
    addEdge(graph, getEdge(0, 4, 5));
    addEdge(graph, getEdge(1, 4, 2));
    addEdge(graph, getEdge(1, 2, 1));
    addEdge(graph, getEdge(2, 3, 4));
    addEdge(graph, getEdge(3, 2, 6));
    addEdge(graph, getEdge(3, 0, 7));
    addEdge(graph, getEdge(4, 1, 3));
    addEdge(graph, getEdge(4, 2, 9));
    addEdge(graph, getEdge(4, 3, 2));

}

vector<Edge *> getPointVex(Graph graph, int v) {
    vector<Edge *> arr;
    for (int i = 0; i < graph.size; ++i) {
        if(graph.edges[i]->r==v)
            arr.push_back(graph.edges[i]);
    }
    return arr;
}


void addEdge(Graph &graph, Edge *edge) {
    graph.edges[graph.size++] = edge;
}

Edge *getEdge(int r, int h, int data) {
    Edge *e = (Edge *) malloc(sizeof(Edge));
    e->data = data;
    e->h = h;
    e->r = r;
    e->flag = false;
    return e;
}


